package leetcode.editor.cn;


import java.util.Arrays;

/**
 * @author: yangwk
 * @date: 2023/3/22
 * @description:
 **/
public class P820ShortEncodingofWords {
    public static void main(String[] args) {
        P820ShortEncodingofWords p820ShortEncodingofWords = new P820ShortEncodingofWords();
        System.out.println(p820ShortEncodingofWords.minimumLengthEncoding(new String[]{"me", "time"}));
    }

//    ["time", "me", "bell"]
//A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].

    public String put(char[] arr, int index, Node root) {
        char c = arr[index];
        int position = c - 'a';
        Node nextNode = root.next[position];
        if (nextNode == null) {
            nextNode = new Node();
            nextNode.setVal(c);
            root.next[position] = nextNode;
            if (index == 0) {
                nextNode.str = new String(arr);
                return null;
            }
        }
        if (index == 0) {
            return nextNode.str;
        }
        return put(arr, index - 1, nextNode);
    }

    public int minimumLengthEncoding(String[] words) {
        Arrays.sort(words, (o1, o2) -> o2.length() - o1.length());
        Node root = new Node();
        StringBuilder stringBuilder = new StringBuilder();
        String split = "#";
        for (String word : words) {
            char[] chars = word.toCharArray();
            String put = put(chars, chars.length - 1, root);
            if (put == null) {
                stringBuilder.append(chars).append(split);
            }
        }
        return stringBuilder.length();
    }

    class Node {
        char val;
        Node[] next = new Node[256];
        String str = "";

        public char getVal() {
            return val;
        }

        public void setVal(char val) {
            this.val = val;
        }

        public Node[] getNext() {
            return next;
        }

        public void setNext(Node[] next) {
            this.next = next;
        }

        public String getStr() {
            return str;
        }

        public void setStr(String str) {
            this.str = str;
        }
    }
}
